Матч 330, Сортируемость (Sortness)

Дивизион 2, Уровень 1

Сортируемостью массива называется среднее арифметическое сортируемости каждого его элемента. Сортируемостью элемента называется количество чисел, больших его и стоящих слева, плюс количество чисел, меньших его и стоящих справа. По заданному массиву натуральных чисел найти его сортируемость.

Класс: Sortness

Метод: double getSortness(vector<int> a)

Ограничения: a содержит от 1 до 50 элементов, массив a содержит все числа от 1 до n (n – количество элементов в массиве a) по одному разу.

Вход. Массив чисел a.

Выход. Сортируемость входного массива.

Пример входа

a

{3,2,1,4,6,7,5,8}

{1,2,3}

{1,5,8,7,9,6,10,12,11,3,4,2}

Пример выхода

1.25

0.0

5.166666666666667

РЕШЕНИЕ

обработка массива

Сортируемость отсортированного по возрастанию массива чисел равна нулю. Если два числа i и j в массиве стоят неправильно (образуют инверсию), то при подсчете сортируемости каждого из этих элементов следует прибавить по единице. Таким образом для решения задачи достаточно подсчитать количество инверсий в массиве, умножить полученно число на 2 и разделить на количество элементов.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class Sortness

{

public:

double getSortness(vector<int> a)

{

int i, j, len = a.size(), res = 0;

for(i = 0; i < len - 1; i++)

for(j = i + 1; j < len; j++)

if (a[i] > a[j]) res += 2;

return (double)res / len;

}

};